package com.sheng.leetcode.year2022.month08.day05;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/08/05
 *
 * 623. 在二叉树中增加一行
 *
 * 给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。
 * 注意，根节点 root 位于深度 1 。
 *
 * 加法规则如下:
 * 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
 * cur 原来的左子树应该是新的左子树根的左子树。
 * cur 原来的右子树应该是新的右子树根的右子树。
 * 如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。
 *
 * 示例 1:
 * 输入: root = [4,2,6,3,1,5], val = 1, depth = 2
 * 输出: [4,1,1,2,null,null,6,3,1,5]
 *
 * 示例 2:
 * 输入: root = [4,2,null,3,1], val = 1, depth = 3
 * 输出:  [4,2,null,1,1,3,null,null,1]
 *
 * 提示:
 *
 * 节点数在 [1, 104] 范围内
 * 树的深度在 [1, 104]范围内
 * -100 <= Node.val <= 100
 * -105 <= val <= 105
 * 1 <= depth <= the depth of tree + 1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/add-one-row-to-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0623 {

    @Test
    public void test01() {
//        TreeNode root = new TreeNode(4);
//        TreeNode left = new TreeNode(2);
//        left.left = new TreeNode(3);
//        left.right = new TreeNode(1);
//        TreeNode right = new TreeNode(6);
//        right.left = new TreeNode(5);
//        root.left = left;
//        root.right = right;
//        int val = 1;
//        int depth = 2;

        TreeNode root = new TreeNode(4);
        TreeNode left = new TreeNode(2);
        left.left = new TreeNode(3);
        left.right = new TreeNode(1);
        root.left = left;
        int val = 1;
        int depth = 3;
        TreeNode treeNode = new Solution().addOneRow(root, val, depth);
        System.out.println(treeNode);
    }
}
class Solution {

    int curDepth;

    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (root == null) {
            return null;
        }
        if (depth == 1) {
            TreeNode treeNode = new TreeNode(val);
            treeNode.left = root;
            return treeNode;
        } else {
            //层序遍历，找到depth的上一层的所有子树
            curDepth = 1;
            List<TreeNode> list = new ArrayList<>();
            list.add(root);
            ergodic(list, val, depth);
            return root;
        }
    }

    public void ergodic(List<TreeNode> list, int val, int depth) {
        if (depth - 1 == curDepth) {
            //对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根
            //cur 原来的左子树应该是新的左子树根的左子树。
            //cur 原来的右子树应该是新的右子树根的右子树。
            for (TreeNode cur : list) {
                TreeNode newLeft = new TreeNode(val);
                newLeft.left = cur.left;
                TreeNode newRight = new TreeNode(val);
                newRight.right = cur.right;
                cur.left = newLeft;
                cur.right = newRight;
            }
        } else {
            //深度不匹配，则继续遍历二叉树的下一层
            List<TreeNode> nodes = new ArrayList<>();
            for (TreeNode treeNode : list) {
                if (treeNode.left != null) {
                    nodes.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    nodes.add(treeNode.right);
                }
            }
            //将深度加1
            curDepth++;
            ergodic(nodes, val, depth);
        }
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
